package com.it.zhangjun.arithmetic.DP;

/**
 * @author jun.zhang6
 * @date 2020/10/27
 */
public class 找零钱 {
    public static void main(String[] args) {
        System.out.println(coins2(41));
    }

    public static int coins2(int n) {
        if (n < -1) {
            return -1;
        }
        int[] dp = new int[n + 1];
        int[] faces = {1, 5, 20, 25};
        for (int face : faces) {
            if (n < face) {
                break;
            }
            dp[face] = 1;
        }
        return coins(n, dp);
    }

    private static int coins(int n, int[] dp) {
        if (n < 1) {
            return Integer.MAX_VALUE;
        }
        if (dp[n] == 0) {
            int min1 = Math.min(coins(n - 25, dp), coins(n - 20, dp));
            int min2 = Math.min(coins(n - 5, dp), coins(n - 1, dp));
            return Math.min(min1, min2) + 1;
        }
        return dp[n];
    }

    public static int coins1(int n) {
        if (n < 1) {
            return Integer.MAX_VALUE;
        }
        if (n == 25 || n == 20 || n == 5 || n == 1) {
            return 1;
        }
        int min1 = Math.min(coins1(n - 1), coins1(n - 5));
        int min2 = Math.min(coins1(n - 20), coins1(n - 25));
        return Math.min(min1, min2) + 1;
    }
}
